Inductive counting below logspace
Identifieur interne : 000296 ( LNCS/Analysis ); précédent : 000295; suivant : 000297Inductive counting below logspace
Auteurs : Carsten Damm [Allemagne] ; Markus Holzer [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1994.
Abstract
Abstract: We apply the inductive counting technique to nondeterministic branching programs and prove that complementation on this model can be done without increasing the width of the branching programs too much. This shows that for an arbitrary space bound s(n), the class of languages accepted by nonuniform nondeterministic O(s(n)) space bounded Turing machines is closed under complementation. As a consequence we obtain for arbitrary space bounds s(n) that the alternation hierarchy of nonuniform O(s(n)) space bounded Turing machines collapses to its first level. This improves the previously known result of Immerman [6] and Szelepcsényi [12] to space bounds of order o(log n) in the nonuniform setting. This reveals a strong difference to the relations between the corresponding uniform complexity classes, since very recently it has been proved that in the uniform case the alternating space hierarchy does not collapse for sublogarithmic space bounds [3, 5, 9].
Url:
DOI: 10.1007/3-540-58338-6_74
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001071
- to stream Istex, to step Curation: 000F60
- to stream Istex, to step Checkpoint: 001259
- to stream Main, to step Merge: 003032
- to stream Main, to step Curation: 002B06
- to stream Main, to step Exploration: 002B06
- to stream LNCS, to step Extraction: 000296
Links to Exploration step
ISTEX:2FE43D8A47994F4BC60DE9B37868841FC85743A2Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Inductive counting below logspace</title><author><name sortKey="Damm, Carsten" sort="Damm, Carsten" uniqKey="Damm C" first="Carsten" last="Damm">Carsten Damm</name></author><author><name sortKey="Holzer, Markus" sort="Holzer, Markus" uniqKey="Holzer M" first="Markus" last="Holzer">Markus Holzer</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:2FE43D8A47994F4BC60DE9B37868841FC85743A2</idno><date when="1994" year="1994">1994</date><idno type="doi">10.1007/3-540-58338-6_74</idno><idno type="url">https://api.istex.fr/document/2FE43D8A47994F4BC60DE9B37868841FC85743A2/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001071</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001071</idno><idno type="wicri:Area/Istex/Curation">000F60</idno><idno type="wicri:Area/Istex/Checkpoint">001259</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001259</idno><idno type="wicri:doubleKey">0302-9743:1994:Damm C:inductive:counting:below</idno><idno type="wicri:Area/Main/Merge">003032</idno><idno type="wicri:Area/Main/Curation">002B06</idno><idno type="wicri:Area/Main/Exploration">002B06</idno><idno type="wicri:Area/LNCS/Extraction">000296</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Inductive counting below logspace</title><author><name sortKey="Damm, Carsten" sort="Damm, Carsten" uniqKey="Damm C" first="Carsten" last="Damm">Carsten Damm</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB IV-Informatik, Universität Trier, D-54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion></affiliation></author><author><name sortKey="Holzer, Markus" sort="Holzer, Markus" uniqKey="Holzer M" first="Markus" last="Holzer">Markus Holzer</name><affiliation wicri:level="4"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Institut für Informatik, Technische Universität München, Arcisstr. 21, D-80290, München</wicri:regionArea><placeName><settlement type="city">Munich</settlement><region type="land" nuts="1">Bavière</region><region type="district" nuts="2">District de Haute-Bavière</region></placeName><orgName type="university">Université technique de Munich</orgName></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1994</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">2FE43D8A47994F4BC60DE9B37868841FC85743A2</idno><idno type="DOI">10.1007/3-540-58338-6_74</idno><idno type="ChapterID">20</idno><idno type="ChapterID">Chap20</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We apply the inductive counting technique to nondeterministic branching programs and prove that complementation on this model can be done without increasing the width of the branching programs too much. This shows that for an arbitrary space bound s(n), the class of languages accepted by nonuniform nondeterministic O(s(n)) space bounded Turing machines is closed under complementation. As a consequence we obtain for arbitrary space bounds s(n) that the alternation hierarchy of nonuniform O(s(n)) space bounded Turing machines collapses to its first level. This improves the previously known result of Immerman [6] and Szelepcsényi [12] to space bounds of order o(log n) in the nonuniform setting. This reveals a strong difference to the relations between the corresponding uniform complexity classes, since very recently it has been proved that in the uniform case the alternating space hierarchy does not collapse for sublogarithmic space bounds [3, 5, 9].</div></front></TEI><affiliations><list><country><li>Allemagne</li></country><region><li>Bavière</li><li>District de Haute-Bavière</li></region><settlement><li>Munich</li></settlement><orgName><li>Université technique de Munich</li></orgName></list><tree><country name="Allemagne"><noRegion><name sortKey="Damm, Carsten" sort="Damm, Carsten" uniqKey="Damm C" first="Carsten" last="Damm">Carsten Damm</name></noRegion><name sortKey="Holzer, Markus" sort="Holzer, Markus" uniqKey="Holzer M" first="Markus" last="Holzer">Markus Holzer</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/LNCS/Analysis
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000296 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/LNCS/Analysis/biblio.hfd -nk 000296 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= LNCS
|étape= Analysis
|type= RBID
|clé= ISTEX:2FE43D8A47994F4BC60DE9B37868841FC85743A2
|texte= Inductive counting below logspace
}}
| This area was generated with Dilib version V0.6.31. |  |